#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=128 lang=cpp
 *
 * [128] 最长连续序列
 */

// @lc code=start
class Solution {
public:
    // 只采用HashSet
    // int longestConsecutive(vector<int>& nums) {
    //     unordered_set<int> record; int res = 0;
    //     for (int i = 0; i < nums.size(); i++) {
    //         record.insert(nums[i]);
    //     }
        
    //     for (int i = 0; i < nums.size(); i++) {
    //         if (!record.count(nums[i] - 1)) {
    //             int now = nums[i]; int cz = 1;
    //             while (record.count(now + 1)) {
    //                 cz++; now++;
    //             }
    //             res = max(res, cz);
    //         }
    //     }
    //     return res;
    // }

    // 采用Hash表的思路, 可以减小遍历的次数
    // int longestConsecutive(vector<int>& nums) {
    //     unordered_map<int, int> mapper; int res = 0;
    //     for (int i = 0; i < nums.size(); i++) mapper.insert({nums[i], i});
    //     for (int i = 0; i < nums.size(); i++) {
    //         if (!mapper.count(nums[i] - 1)) {
    //             int num = nums[i];
    //             while (mapper.count(num + 1)) {
    //                 num = nums[mapper[num + 1]];
    //             }
    //             mapper.insert({nums[i], mapper[num]}); // 更新map
    //             res = max(res, num - nums[i] + 1);
    //         }
    //     }
    //     return res;
    // }

    // hash动态规划
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> dp; int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (!dp[nums[i]]) {
                int l = dp[nums[i] - 1], r = dp[nums[i] + 1];
                int len = l + r + 1;
                res = max(res, len);
                dp[nums[i]] = len;
                dp[nums[i] - l] = len;
                dp[nums[i] + r] = len;
            }
        }
        return res;
    }

};
// @lc code=end

